package cn.itcast.algorithm.search;

/**
 * 循环数组 -- 部分有序 查询目标值在该数组中的索引
 * (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
 *
 * Example 1:
 *  Input: nums = [4,5,6,7,0,1,2], target = 0
 *  Output: 4
 *
 * Example 2:
 *  Input: nums = [4,5,6,7,0,1,2], target = 3
 *  Output: -1
 * create by zhangtian3 on 2019/4/10
 */
public class RotatedSortedArraySearch {
    public static int searchRotatedSortedArray(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return -1 ;
        }

        int low = 0 ;
        int high = nums.length - 1 ;

        while(low <= high){
            int mid = low + (high - low) / 2 ;
            if(nums[mid] == target){
                return mid ;
            }else if (nums[mid] < nums[high]){ // 与右边端点比较  左右两边再判断
                if (nums[mid] < target && target <= nums[high]) { // 目标值在右边
                    low = mid + 1 ;
                }else { // 目标值在左边
                    high = mid - 1 ;
                }
            }else {// 与右边端点比较 左右两边再判断
                if(nums[mid] > target && target >= nums[low]){// 目标值在左边
                    high = mid - 1 ;
                }else {// 目标值在右边
                    low = mid + 1 ;
                }
            }
        }

        return -1 ;
    }

    public static void main(String[] args) {
        int[] arr = {5, 1, 3} ;
        int value = 5 ;
        System.out.println(searchRotatedSortedArray(arr, value));
        System.exit(0);
    }
}
